package dynamicProgramming.bagQuestion;


//有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
//
//        问最多能装入背包的总价值是多大?
public class Bag02 {


    public int backPackII(int m, int[] a, int[] v) {
        // write your code here
        int[][]dp=new int[a.length+1][m+1];
        for (int index = 1; index<=a.length; index++) {
            for (int rest = 1; rest <=m; rest++) {
                if (a[index-1]>rest){
                    dp[index][rest]=dp[index-1][rest];
                }else {
                    dp[index][rest]=Math.max(v[index-1]+dp[index-1][rest-a[index-1]],dp[index-1][rest]);
                }
            }
        }
        return  dp[a.length][m];


    }



}
